#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@his-pc>
#
# Distributed under terms of the MIT license.

"""

"""


class Solution:
    """
    @param word1: A string
    @param word2: A string
    @return: The minimum number of steps.
    """
    def minDistance(self, word1, word2):
        # write your code here
        rows, cols = len(word1), len(word2)
        self.records = self.make_matrix(rows+1, cols+1, list(range(cols+1)), list(range(rows+1)))
        print(self.records)

        for row in range(1, rows+1):

            for col in range(1, cols+1):
                if word1[row-1] == word2[col-1]:
                    self.records[row][col] = self.records[row-1][col-1]
                else:
                    self.records[row][col] = min(
                        self.records[row-1][col],
                        self.records[row][col-1],
                        self.records[row-1][col-1]
                    ) + 1
                    # self.records[row][col] = self.records[row-1][col-1] + 1

        return self.records[-1][-1]

    def make_matrix(self, rows, cols, first_row_values, first_col_values, init_value=None):
        one_row = [init_value] * cols
        mat = [list(one_row) for i in range(rows)]

        mat[0] = first_row_values       # init first row

        # init first col
        for row in range(rows):
            mat[row][0] = first_col_values[row]

        return mat


def main():
    print("start main")
    s = Solution()
    # ret = s.minDistance('abcd', 'dbca')
    ret = s.minDistance('ab', 'a')
    print(ret)

if __name__ == "__main__":
    main()
